package dp;

//硬币问题，给定有1毛，2毛，5毛的硬币，求当给出一个数值时，使用最少的硬币组合成该数字
public class CoinProblem {
	// 用以表示硬币的面值
	public static final int[] vj = { 1, 2, 5 };

	// d(i)用来表示凑够i元需要的最少的硬币
	// 递推公式为d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;
	public static void main(String[] args) {
		for (int test = 0; test <= 20; test++) {
			getMinCoins(test);
		}
	}

	public static void getMinCoins(int i) {
		// 新建一个数组用来存储i毛最少的硬币数
		int[] minCount = new int[i + 1];
		minCount[0] = 0;
		for (int k = 1; k <= i; k++) {
			int temp = 0, min = minCount[k - vj[0]] + 1; // 用减1毛的硬币数来暂存最小值
			minCount[k] = min;
			for (int j = 1; j < vj.length; j++) {
				if (k - vj[j] >= 0) {
					temp = minCount[k - vj[j]] + 1;
					// 找到所有的最小值
					if (temp < min) {
						min = temp;
						minCount[k] = temp;
					}
				}
			}
		}
		System.out.print(minCount[i] + " ");
	}

}
